#include <vector>
#include <string>
using namespace std;
/*
 * @lc app=leetcode.cn id=79 lang=cpp
 *
 * [79] 单词搜索
 */

// @lc code=start
int dxdy[][4] = {
    {1, -1, 0, 0},
    {0, 0, 1, -1}
};
    
class Solution {
public:
    bool exist(vector<vector<char>>& board, string word) {
        if (board.size() * board[0].size() < word.size()) return false;
        for (int i = 0; i < board.size(); i++) {
            for (int j = 0; j < board[0].size(); j++) {
                if (word[0] == board[i][j] && dfs(i, j, 1, board, word)) {
                    return true;
                }
            }
        }
        return false;
    }

    bool dfs(int x, int y, int index, vector<vector<char>> & used, const string & word) {
        if (word.length() == index) return true;
        for (int i = 0; i < 4; i++) {
            int nx = x + dxdy[0][i], ny = y + dxdy[1][i];
            if (nx >= 0 && nx < used.size() && ny >= 0 && ny < used[0].size() && used[nx][ny] == word[index]) {
                char t = used[x][y]; used[x][y] = '\0';
                bool res = dfs(nx, ny, index + 1, used, word);
                used[x][y] = t;
                if (res) return true;
            }
        }
        return false;

    }
};
// @lc code=end

